package de.hwr.sudokuspielehr.data;

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

/**
 * Sudoku class.
 * 
 * @author J. Reischauer
 * 
 */
public class Sudoku {
	/**
	 * Value returned if no empty cell is left in the Sudoku.
	 */
	private static final int DEFAULT_INDEX = -1;

	/**
	 * Value for empty cells.
	 */
	public static final int EMPTY_CELL_VALUE = -1;

	/**
	 * Number of cells in the Sudoku.
	 */
	public static final int CELL_COUNT = 9 * 9;

	/**
	 * Point returned if no empty cell is left in the Sudoku.
	 */
	public static Point DEFAULT_COORD = null;

	/**
	 * Sudoku board.
	 */
	private int[] board;

	/**
	 * Sudoku board in its initial state.
	 */
	private int[] initialBoard;

	/**
	 * Solved version of the board.
	 */
	private int[] solvedBoard;

	/**
	 * Creation info.
	 */
	private String creationInfo;

	/**
	 * Difficulty.
	 */
	private String difficulty;

	/**
	 * Constructs a new Sudoku.
	 * 
	 * @param pGroupEdgeLength
	 *            edge length of a single group of numbers in the Sudoku.
	 */
	public Sudoku() {
		board = new int[CELL_COUNT];
		initialBoard = new int[CELL_COUNT];
		solvedBoard = new int[CELL_COUNT];
		creationInfo = "";
		difficulty = "";
		unsetBoard();
	}

	/**
	 * Sets values of all cells of this Sudoku to default value.
	 */
	public void unsetBoard() {
		for (int i = 0; i < CELL_COUNT; i++) {
			board[i] = EMPTY_CELL_VALUE;
		}
	}

	/**
	 * Allows access to the internal array.
	 * 
	 * @return int array
	 */
	public int[] getBoard() {
		return board;
	}

	/**
	 * Sets the new Sudoku board.
	 * 
	 * @param pBoard
	 *            new board
	 */
	public void setBoard(int[] pBoard) {
		board = pBoard;
	}

	/**
	 * 
	 * @return
	 */
	public int[] getInitialBoard() {
		return initialBoard;
	}

	/**
	 * 
	 * @param pBoard
	 */
	public void setInitialBoard(int[] pBoard) {
		initialBoard = pBoard;
	}

	/**
	 * 
	 * @return
	 */
	public int[] getSolvedBoard() {
		return solvedBoard;
	}

	/**
	 * 
	 * @return
	 */
	public void setSolvedBoard(int[] pBoard) {
		solvedBoard = pBoard;
	}

	/**
	 * Returns the value of the cell at the given XY coordinate. <br>
	 * 0 based.
	 * 
	 * @param pX
	 *            x coordinate of the cell to get value from
	 * @param pY
	 *            y coordinate of the cell to get value from
	 * @return value of cell at given XY coordinate
	 */
	public int getCell(int pX, int pY) {
		int index = coordinatesToIndex(pX, pY);
		return board[index];
	}

	/**
	 * Sets the new value for the cell at the given XY coordinate.
	 * 
	 * @param pX
	 *            x coordinate of the cell to set new value for
	 * @param pY
	 *            y coordinate of the cell to set new value for
	 * @param pValue
	 *            new value for the cell
	 */
	public void setCell(int pX, int pY, int pValue) {
		int index = coordinatesToIndex(pX, pY);
		board[index] = pValue;
	}

	/**
	 * 
	 * @param pIndex
	 * @return
	 */
	public int getCell(int pIndex) {
		return board[pIndex];
	}

	/**
	 * Sets the new value for the cell at the given index.
	 * 
	 * @param pIndex
	 *            index of the cell to set new value for
	 * @param pValue
	 *            new value for the cell
	 */
	public void setCell(int pIndex, int pValue) {
		board[pIndex] = pValue;
	}

	/**
	 * Solves all cells with scan technique.
	 */
	public void scan() {
		boolean repeat = false;
		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				for (int i = 1; i <= 9; i++) {
					boolean foundSomething = scanSingleGroupForNumber(x, y, i);
					if (foundSomething) {
						repeat = true;
					}
				}
			}
		}

		if (repeat) {
			scan();
		}
	}

	/**
	 * Returns the group at the given x y location in the sudoku.
	 * 
	 * @param pX
	 *            x coord
	 * @param pY
	 *            y coord
	 * @return the group as two-dimensional array
	 */
	public int[][] getGroup(int pX, int pY) {
		if (pX < 0 || pX > 2 || pY < 0 || pY > 2) {
			throw new RuntimeException("x or y coord out of range");
		}

		int startingX = pX * 3;
		int startingY = pY * 3;
		int[][] group = new int[3][3];

		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				group[x][y] = getCell(startingX + x, startingY + y);
			}
		}

		return group;
	}

	/**
	 * Checks if this Sudoku contains errors.
	 * 
	 * @return true if this Sudoku contains erros, false if not
	 */
	public boolean containsErrors() {
		return (errorInRows() || errorInCols() || errorInGroups());
	}

	/**
	 * Returns the index of the next empty cell, startin at the given index.
	 * 
	 * @param pStartingIndex
	 *            starting index
	 * @return index of the next empty cell
	 */
	public int getNextEmptyCellIndex(int pStartingIndex) {
		for (int i = pStartingIndex; i < board.length; i++) {
			if (board[i] == EMPTY_CELL_VALUE) {
				return i;
			}
		}

		return DEFAULT_INDEX;
	}

	/**
	 * Returns the xy coordinates of the next empty cell, starting to search at
	 * the given x and y coordinates in this Sudoku.
	 * 
	 * @param pStartingX
	 *            starting x coordinate
	 * @param pStartingY
	 *            starting y coordinate
	 * @return xy coordinates of the next empty cell as a bew instance of
	 *         Dimension, null if there is no empty cell left in the given
	 *         Sudoku
	 */
	public Point getNextEmptyCell(int pStartingX, int pStartingY) {
		int nextEmptyCellIndex = getNextEmptyCellIndex(coordinatesToIndex(pStartingY, pStartingY));
		return indexToCoordinates(nextEmptyCellIndex);
	}

	/**
	 * Fills the next cell that only has one possible number left.
	 * 
	 * @return true if an obvious field was found and filled, false if no
	 *         obvious field was found
	 */
	public boolean fillNextObviousCell() {
		int[] board = getBoard();

		for (int i = 0; i < board.length; i++) {
			if (board[i] == EMPTY_CELL_VALUE) {
				List<Integer> possibleNumbers = getPossibleNumbers(i);
				if (possibleNumbers.size() == 1) {
					board[i] = possibleNumbers.get(0);
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * Fills all obvious cells of this sudoku.
	 */
	public void fillAllObviousCells() {
		boolean done = false;
		while (!done) {
			if (fillNextObviousCell() == false) {
				done = true;
			}
		}
	}

	/**
	 * Determines whether or not this board is completely filled with numbers or
	 * not.
	 * 
	 * @return
	 */
	public boolean isFilled() {
		for (int i : getBoard()) {
			if (i == EMPTY_CELL_VALUE) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 
	 * @param pIndex
	 * @return
	 */
	public List<Integer> getPossibleNumbersA(int pIndex) {
		if (getBoard()[pIndex] != -1) {
			return new ArrayList<Integer>();
		}

		Point p = indexToCoordinates(pIndex);
		List<Integer> result = new ArrayList<Integer>();

		int groupX = p.x / 3;
		int groupY = p.y / 3;

		for (int currentNumber = 1; currentNumber <= 9; currentNumber++) {
			if (!numberInGroup(groupX, groupY, currentNumber) && !numberInLine(p.x, p.y, currentNumber, true) && !numberInLine(p.x, p.y, currentNumber, false)) {
				result.add(currentNumber);
			}
		}

		return result;
	}

	/**
	 * 
	 * @param pX
	 * @param pY
	 * @param pNumber
	 * @param pHorizontal
	 * @return
	 */
	private boolean numberInLine(int pX, int pY, int pNumber, boolean pHorizontal) {
		for (int i = 0; i < 9; i++) {
			if (pHorizontal) {
				if (getCell(i, pY) == pNumber) {
					return true;
				}
			} else {
				if (getCell(pX, i) == pNumber) {
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * 
	 * @param pGroupX
	 * @param pGroupY
	 * @param pNumber
	 * @return
	 */
	private boolean numberInGroup(int pGroupX, int pGroupY, int pNumber) {
		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				int currentX = pGroupX * 3 + x;
				int currentY = pGroupY * 3 + y;

				if (getCell(currentX, currentY) == pNumber) {
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * Determines all possible numbers for a cell in the given Sudoku.
	 * 
	 * @param pX
	 *            x coordinate of the Sudoku
	 * @param pY
	 *            y coordinate of the Sudoku
	 * @return List containing all numbers possible for the specified cell in
	 *         the given Sudoku
	 */
	public List<Integer> getPossibleNumbers(int pX, int pY) {
		return getPossibleNumbers(coordinatesToIndex(pX, pY));
	}

	/**
	 * 
	 * @param pIndex
	 * @return
	 */
	public List<Integer> getPossibleNumbers(int pIndex) {
		List<Integer> result = new ArrayList<Integer>();

		for (int i = 1; i <= 9; i++) {
			getBoard()[pIndex] = i;
			if (!containsErrors()) {
				result.add(i);
			}
			getBoard()[pIndex] = EMPTY_CELL_VALUE;
		}
		return result;
	}

	/**
	 * Recursively solves this Sudoku.
	 * 
	 */
	public void solve() {
		solveA();
		setSolvedBoard(getBoard());
	}

	/**
	 * Prints the Sudoku board to the screen.
	 */
	public void print() {
		for (int i = 0; i < board.length; i++) {

			Point currentCoords = indexToCoordinates(i);
			int currentValue = getCell(currentCoords.x, currentCoords.y);

			if (currentValue == -1) {
				System.out.print("  -");
			} else {
				System.out.print("  " + currentValue);
			}

			if (i != 0 && ((i + 1) % 9 == 0)) {
				System.out.println();
			}
		}

		System.out.println("--------------------------------");
	}

	/**
	 * 
	 */
	public Sudoku clone() {
		Sudoku s = new Sudoku();
		s.setBoard(getBoard().clone());
		s.setInitialBoard(getInitialBoard().clone());
		s.setSolvedBoard(getSolvedBoard().clone());
		return s;
	}

	/**
	 * Scan group (x|y) for a given number.
	 * 
	 * @param pX
	 *            x coord of group
	 * @param pY
	 *            y coord of group
	 * @param pNumber
	 *            number to scan for
	 */
	public boolean scanSingleGroupForNumber(int pX, int pY, int pNumber) {
		int[][] group = getGroup(pX, pY);
		if (groupContains(group, pNumber)) {
			return false;
		}

		boolean[][] possibleCells = getEmptyCellsOfGroup(group);
		int[][] vertRelatedGroup1 = getGroup(pX, (pY + 1) % 3);
		int[][] vertRelatedGroup2 = getGroup(pX, (pY + 2) % 3);
		int[][] horiRelatedGroup1 = getGroup((pX + 1) % 3, pY);
		int[][] horiRelatedGroup2 = getGroup((pX + 2) % 3, pY);

		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				if (vertRelatedGroup1[x][y] == pNumber || vertRelatedGroup2[x][y] == pNumber) {
					removeLineFromPossibleCells(possibleCells, x, false);
				}
				if (horiRelatedGroup1[x][y] == pNumber || horiRelatedGroup2[x][y] == pNumber) {
					removeLineFromPossibleCells(possibleCells, y, true);
				}
			}
		}

		int count = 0;
		int xCoord = -1;
		int yCoord = -1;

		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				if (possibleCells[x][y] == true) {
					count++;
					xCoord = x;
					yCoord = y;
				}
			}
		}

		if (count == 1) {
			setCell(pX * 3 + xCoord, pY * 3 + yCoord, pNumber);
			return true;
		}

		return false;
	}

	/**
	 * 
	 * @param pGroup
	 * @return
	 */
	private boolean[][] getEmptyCellsOfGroup(int[][] pGroup) {
		boolean[][] result = new boolean[3][3];
		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				if (pGroup[x][y] == EMPTY_CELL_VALUE)
					result[x][y] = true;
			}
		}
		return result;
	}

	/**
	 * 
	 * @param pPossibleCells
	 * @param pLineNumber
	 * @param pHorizontal
	 */
	private void removeLineFromPossibleCells(boolean[][] pPossibleCells, int pLineNumber, boolean pHorizontal) {
		for (int i = 0; i < 3; i++) {
			if (pHorizontal) {
				pPossibleCells[i][pLineNumber] = false;
			} else {
				pPossibleCells[pLineNumber][i] = false;
			}
		}
	}

	/**
	 * 
	 * @param pGroup
	 * @param pNumber
	 * @return
	 */
	private boolean groupContains(int[][] pGroup, int pNumber) {
		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				if (pGroup[x][y] == pNumber) {
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * Recursively solves this Sudoku.
	 * 
	 * @return
	 */
	private boolean solveA() {
		int currentIndex = getNextEmptyCellIndex(0);

		if (currentIndex == DEFAULT_INDEX) {
			return true;
		}

		int oldValue = getCell(currentIndex);

		for (int i = 1; i <= 9; i++) {
			setCell(currentIndex, i);

			if (containsErrors()) {
				continue;
			} else {
				if (getNextEmptyCellIndex(0) == DEFAULT_INDEX) {
					return true;
				} else {
					boolean nextSolveSucceeded = solveA();
					if (!nextSolveSucceeded) {
						continue;
					} else {
						return true;
					}
				}
			}
		}

		setCell(currentIndex, oldValue);
		return false;
	}

	/**
	 * Checks if this Sudoku contain errors.
	 * 
	 * @return true if a group in this Sudoku contains an error
	 */
	private boolean errorInGroups() {
		// each row - i is y coord of current group
		for (int i = 0; i < 3; i++) {
			// each col - j is x coord of current group
			for (int j = 0; j < 3; j++) {
				boolean[] numbers = new boolean[10];
				// each sub row - k is y coord of current cell
				for (int k = 0; k < 3; k++) {
					int currentY = i * 3 + k;
					// each sub col - l is x coord of current cell
					for (int l = 0; l < 3; l++) {
						int currentX = j * 3 + l;

						int currentNumber = getCell(currentX, currentY);

						if (currentNumber != EMPTY_CELL_VALUE) {
							// check if number valid
							isValidNumber(currentNumber);

							if (!numbers[currentNumber]) {
								numbers[currentNumber] = true;
							} else if (numbers[currentNumber]) {
								// error found
								return true;
							}
						}
					}
				}
			}
		}
		return false;
	}

	/**
	 * Checks if the rows of this Sudoku contain an error.
	 * 
	 * @return true if rows contain error, false if not
	 */
	private boolean errorInRows() {
		return errorInLines(true);
	}

	/**
	 * Checks if the columns of this Sudoku contain an error.
	 * 
	 * @return true if cols contain error, false if not
	 */
	private boolean errorInCols() {
		return errorInLines(false);
	}

	/**
	 * Determines whether or not this Sudoku, in its current state, contains
	 * errors in its rows or cols.
	 * 
	 * @param pHorizontal
	 *            if true: checks rows, if false: checks columns
	 * @return true if this Sudoku does not contain errors, false if it does
	 */
	private boolean errorInLines(boolean pHorizontal) {
		// foreach row
		for (int i = 0; i < 9; i++) {
			// a value for each possible number in the row - true if the number
			// was previously found in the row
			boolean[] numbers = new boolean[10];
			// foreach col
			for (int j = 0; j < 9; j++) {
				int currentNumber;

				if (pHorizontal) {
					currentNumber = getCell(i, j);
				} else {
					currentNumber = getCell(j, i);
				}

				if (currentNumber != EMPTY_CELL_VALUE) {
					// check if number valid
					isValidNumber(currentNumber);

					// check if number already in row
					if (!numbers[currentNumber]) {
						// if not already in row - now it was found in row
						numbers[currentNumber] = true;
					} else if (numbers[currentNumber]) {
						// error found
						return true;
					}
				}
			}
		}
		return false;
	}

	/**
	 * Translates the associated index of a cell to board coordinates.
	 * 
	 * @param pIndex
	 *            the given index
	 * @return board coordinates of the given index
	 */
	private static Point indexToCoordinates(int pIndex) {
		if (pIndex == DEFAULT_INDEX) {
			return DEFAULT_COORD;
		}

		int x = pIndex % 9;
		int y = (pIndex - x) / 9;
		return new Point(x, y);

	}

	/**
	 * Translates board coordinates to the associated index within the board
	 * array.
	 * 
	 * @param pX
	 *            x coordinate, starting with 0
	 * @param pY
	 *            y coordinate, starting with 0
	 * @return the index if the associated field within the board array
	 */
	private static int coordinatesToIndex(int pX, int pY) {
		return 9 * pY + pX;
	}

	/**
	 * Checks whether or not the given number is in the valid range of numbers
	 * or not.
	 * 
	 * @param pNumber
	 *            the given number
	 * @return true if it is in the valid range of numbers, false if not
	 */
	private static boolean isValidNumber(int pNumber) {
		if (pNumber < 1 && pNumber > 9) {
			return false;
		} else {
			return true;
		}
	}

	public String getCreationInfo() {
		return creationInfo;
	}

	public void setCreationInfo(String pCreationInfo) {
		creationInfo = pCreationInfo;
	}

	public void setDifficulty(String pDifficulty) {
		difficulty = pDifficulty;
	}

	public String getDifficulty() {
		return difficulty;
	}
}
